package com.hao.algorithms;

/**
 * TODO
 *
 * @author 97472
 * @version 1.0
 * @date 2021/4/6 16:56
 */
public class Algorithms {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Algorithms algorithms = new Algorithms();
        System.out.println(algorithms.power2BF_I(2));
        long spendTime = System.currentTimeMillis()-start;
        System.out.println("time:"+spendTime);
//        int a = 1;
//        int b = 2;
//        a ^= b;
//        b ^= a;
//        a ^= b;
//        System.out.println("a = "+a+";b = "+b);
    }

    /**
     *  起泡排序
     * @param arr 需要排序的数组
     */
    public void bubbleSort(int[] arr){
        while(!scanSwap(arr));
    }

    /**
     *  数组元素交换
     * @param arr 数组
     * @param index1 元素1角标
     * @param index2 元素2角标
     */
   private void swap(int[] arr, int index1,int index2){
        int temp = arr[index2];
        arr[index2] = arr[index1];
        arr[index1] = temp;
   }

    /**
     * 扫描交换并检查是否已经有序
     * @param arr 需要扫描交换的数组
     * @return
     */
   private boolean scanSwap(int[] arr){
       // 默认是已经排过序
       boolean isSort = true;
       // 进行扫描交换
       for (int i = 0; i < arr.length-1; i++) {
           if (arr[i] > arr[i+1]){
               swap(arr,i,i+1);
               isSort=false;
           }
       }
       return isSort;
   }

    /**
     *  最原始的版本，获取一个十进制的整数，二进制中1的数量，时间复杂度为O(logn)
     * @param n
     * @return
     */
   public int countOnes1(int n){
       int count = 0;
       while (n > 0){
           boolean isOne = n%2 == 1;
           if (isOne){
                count++;
           }
           n /=2;
        }
       return count;
   }
   /**
     *  使用增强的版本，获取一个十进制的整数，二进制中1的数量，时间复杂度为O(logn)
    *   该算法用到了两个关键的
    *   1，n & 1 与运算。&运算 两个数的二进制的位置上的数如果都是1，那么结果也是1，否则就为0
    *   例子： 整数5 二进制 0000 0000 0000 0101
    *         整数1 二进制 0000 0000 0000 0001 &运算
    *         整数1 二进制 0000 0000 0000 0001
    *
    *   小知识：任何数与1进行&运算，都可以识别其二进制的最后一位是否是1。是1结果就是1否则就为0.
    *           当然也可以通过上面的结论再排除2就能获取其奇偶性
    *
    *   2，移位 n >> 1,移位有<< >> >>>左移位，右有符号移位和右无符号移位
    *      移位好理解，即一个数的二进制数整体向左向右移动，多余的清楚，缺失部分使用0填充
    *      要注意的是，有符号右移是指，当为负数的时候代表正负的二进制位置不变，其他位置移动。
    *      而无符号右移会带着代表正负的二进制位置一起整体移动。
    *   例子： 整数5 二进制 0000 0000 0000 0101 向左移动1
    *         整数10二进制 0000 0000 0000 1010
     * @param n
     * @return
     */
   public int countOnes2(int n){
       int count = 0;
       while (n > 0){
//           检查最右一位是否是1
           count += (n & 1);
//           往右移一位
           n >>= 1;
       }
       return count;
   }

    /**
     * 增强版本，获取一个十进制的整数，二进制中1的数量，时间复杂度为O(countOnes) 与二进制中的1成正比
     * 重点:n &= (n-1);
     *对于任意整数n，不妨设其最低（右）的数位1对应于2^k，于是n的二进制展开应该如下：
     * x x ... x 1 0 0 ... 0
     * 其中数位x可能是0或1，而最低的k + 1位必然是" 1 0 0 ... 0 "，即数位1之后是k个0。
     * 于是相应地，n - 1的二进制展开应该如下：
     * x x ... x 0 1 1 ... 1
     * 也就是说，其最低的k + 1位与n恰好相反，其余的（更高）各位相同。
     * 因此，二者做位与运算（n & (n - 1)）的结果应为：
     * x x ... x 0 0 0 ... 0
     * 等效于将原n二进制展开中的最右位的1转置为0
     * @param n
     * @return
     */
   public int countOnes3(int n){
       int count = 0;
       while (n > 0){
           count ++;
           n &= (n-1);
       }
       return count;
   }

    /**
     *  对任意非负整数n，计算2^n
     * @param n
     * @return
     */
   public int power2BF_I(int n){
       if (n < 1){
           return 1;
       }else {
           return power2BF_I(n-1) << 1;
       }
   }

}
